<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>4539：[Hnoi2016]树</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Hnoi2016]树</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Hnoi2016]树</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Hnoi2016]树                </h1>
                <p>时间限制：40s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：256MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p>　　小A想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小A只有一棵结点数为N的树，结<br />
点的编号为1,2,&hellip;,N，其中结点1为根；我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过<br />
程如下：（1）将模板树复制为初始的大树。（2）以下(2.1)(2.2)(2.3)步循环执行M次（2.1）选择两个数字a,b，<br />
其中1&lt;=a&lt;=N，1&lt;=b&lt;=当前大树的结点数。（2.2）将模板树中以结点a为根的子树复制一遍，挂到大树中结点b的下<br />
方(也就是说，模板树中的结点a为根的子树复制到大树中后，将成为大树中结点b的子树)。（2.3）将新加入大树<br />
的结点按照在模板树中编号的顺序重新编号。例如，假设在进行2.2步之前大树有L个结点，模板树中以a为根的子<br />
树共有C个结点，那么新加入模板树的C个结点在大树中的编号将是L+1,L+2,&hellip;,L+C；大树中这C个结点编号的大小<br />
顺序和模板树中对应的C个结点的大小顺序是一致的。下面给出一个实例。假设模板树如下图：</p>
<p><img width="312" height="165" alt="" src="../file/4539_0.png" /><br />
根据第(1)步，初始的大树与模板树是相同的。在(2.1)步，假设选择了a=4，b=3。运行(2.2)和(2.3)后，得到新的<br />
大树如下图所示<br />
<img width="340" height="232" alt="" src="../file/4539_1.png" /><br />
现在他想问你，树中一些结点对的距离是多少。</p></p><hr/><h3>输入格式</h3><p><p>　　第一行三个整数：N,M,Q，以空格隔开，N表示模板树结点数，M表示第(2)中的循环操作的次数，Q 表示询问数<br />
量。接下来N-1行，每行两个整数 fr,to，表示模板树中的一条树边。再接下来M行，每行两个整数x,to，表示将模<br />
板树中 x 为根的子树复制到大树中成为结点to的子树的一次操作。再接下来Q行，每行两个整数fr,to，表示询问<br />
大树中结点 fr和 to之间的距离是多少。<span style="font-family: Arial; font-size: 14px; line-height: 23.7999992370605px;">N,M,Q&lt;=100000</span></p></p><hr/><h3>输出格式</h3><p><p>　　输出Q行，每行一个整数，第 i行是第 i个询问的答案。</p></p><hr/><h3>样例输入</h3><pre>5 2 3 
1 4 
1 3 
4 2 
4 5 
4 3 
3 2 
6 9 
1 8 
5 3 </pre><hr/><h3>样例输出</h3><pre>6
3
3</pre><hr/><h3>提示</h3><p><p>经过两次操作后，大树变成了下图所示的形状：<br />
<img width="347" height="230" alt="" src="../file/4539_0.png" /><br />
结点6到9之间经过了6条边，所以距离为6；类似地，结点1到8之间经过了3条边；结点5到3之间也经过了3条边。</p></p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=4539" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=4539" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>